[LeetCode 461] Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note: $\ 0 ≤ x, y < 2^{31}.$

题目类型分析

题目要求汉明距离，即统计 2 个数在二进制形式下，不同二进制位的数量。
开始没有思路，只能判断出它不是考查数据结构、也不是某种算法的应用，先归入数学类应该是比较稳妥的。

解法

1. 暴力求解法
   没有思路的情况下最容易想到暴力求解法，大概的流程如下：

   • 比较 x, y，假设 x 为二者中较大的一个，并以它为比较基准
   • 将 x, y 分别转换为二进制字符串，并将位数对齐
   • 从 x 的 LSB 开始，循环比较 y 对应位置的二进制位
   • 如果相同，计数不变；如果不同，计数+1
   • 循环结束，返回计数结果

   边界情况：如果 x, y 相等，那么直接返回 0；否则按照上述流程进行计算

   缺陷：存在大量的字符串拼接操作，也保存了完整的二进制字符串。考虑上述两个缺陷，改进的思路有了：1.不使用字符串，考虑直接使用数值进行比较 2. 不保存完整的二进制位，逐位比较完毕后直接丢弃，于是有了下面的解法。

2. 改进一点的暴力求解法
   用“除二取余法”通过数值计算逐位获取二进制表示，同时完成比较，每次比较完毕后就丢弃结果。与上面提到的改进方向一致，大致流程如下：

   • x, y 分别对 2 取余数
   • 余数相同，则计数+1；否则不变
   • x, y 分别除以 2，不能整除则向下取整
   • 重复以上步骤，直至 x, y 均为 0 时，结束循环，返回计数

   边界情况： 同上

   缺陷：比方法 1 节省了字符串操作和存储，但仍然需要循环计算。

   能不能免去循环计算的过程呢？当然可以，请看下文。

3. 利用数学原理求解
   查一下 wiki，汉明距离的标准算法就是 2 个数进行逻辑异或，结果中只包含二者不同的二进制位（也就是'1'），那么把结果中 1 的个数统计出来就是答案。（逻辑运算真是太美好了！）这个方法完整步骤太简单，就不写了。

   边界情况：同上

   缺陷： 继承了方法 2 的优点，不仅免去了循环计算，还更容易理解，重要结果一步就可以得到，应该是最优方案了吧。